import java.util.Stack;

public class Solution {
      //JZ84 二叉树中和为某一值的路径(三)
    //哈希桶
    //递归遍历
    public static int count=0;
    public void dfs(TreeNode root,int sum){
        if(root==null){
            return ;
        }
        sum=sum-root.val;
        if(sum==0){
            count++;
        }
        dfs(root.left,sum);
        dfs(root.right,sum);

    }
    public int FindPath (TreeNode root, int sum) {
        if(root==null){
            return 0;
        }
        dfs(root,sum);
        FindPath(root.left,sum);
        FindPath(root.right,sum);
        return count;
    }
//JZ82 二叉树中和为某一值的路径(一)
    //用桟的方法
    class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }
    /**
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return bool布尔型
     */
    public boolean hasPathSum (TreeNode root, int sum) {
         if(root==null){
             return false;
         }
         Stack<TreeNode> stack=new Stack<TreeNode>();
         Stack<Integer>s1=new Stack<>();
         stack.push(root);
         s1.push(root.val);
          while(!stack.empty()){
              TreeNode cur=stack.pop();
                int total=s1.pop();
              if(cur.left==null&&cur.right==null&&sum==total){
                  return true;
              }
              if(cur.right!=null){
                  stack.push(cur.right);
                 s1.push(total+cur.right.val);

              }
              if(cur.left!=null){
                  stack.push(cur.left);
                  s1.push(total+cur.left.val);

              }
          }
          return false;
    }
}